//给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。 
//
// 只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。 
//
// 在完成所有删除操作后，请你返回列表中剩余区间的数目。 
//
// 
//
// 示例： 
//
// 
//输入：intervals = [[1,4],[3,6],[2,8]]
//输出：2
//解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= intervals.length <= 1000 
// 0 <= intervals[i][0] < intervals[i][1] <= 10^5 
// 对于所有的 i != j：intervals[i] != intervals[j] 
// 
// Related Topics数组 | 排序 
//
// 👍 81, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;

class RemoveCoveredIntervals {
    public static void main(String[] args) {
        Solution solution = new RemoveCoveredIntervals().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // https://mp.weixin.qq.com/s/Eb6ewVajH56cUlY9LetRJw
        public int removeCoveredIntervals(int[][] intervals) {
            // 起点升序，终点降序排列
            Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);

            int res = 0;  // 记录合并的区间个数
            int left = intervals[0][0], right = intervals[0][1];
            int length = intervals.length;
            for (int i = 1; i < length; i++) {
                int[] interval = intervals[i];
                // 可以合并区间，这种情况
                // ——————————
                //   ————
                if (interval[0] >= left && interval[1] <= right) {
                    res++;
                }

                // 更新区间，但不能合并
                // ——————————
                //       ————————
                if (interval[0] <= right && interval[1] > right) {
                    right = interval[1];
                }

                // 两个区间，需要同时更新左右边界
                // —————————
                //              ——————
                if (interval[0] > right) {
                    left = interval[0];
                    right = interval[1];
                }
            }

            // 返回没有合并的区间
            return length - res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
